package com.lihepeng.leecode.solid_aim_offer.linkedlist;

import com.lihepeng.leecode.linkedList.ListNode;

/**
 * 环的入口节点
 * 给一个长度为n链表，若其中包含环，请找出该链表的环的入口结点，否则，返回null。
 *
 * 数据范围： n\le10000n≤10000，1<=结点值<=100001<=结点值<=10000
 * 要求：空间复杂度 O(1)O(1)，时间复杂度 O(n)O(n)
 *
 * 例如，输入{1,2},{3,4,5}时，对应的环形链表如下图所示：
 */
public class Solution23 {
    /**
     * 使用快慢指针 方案来实现
     * @param pHead
     * @return
     */
    public ListNode EntryNodeOfLoop(ListNode pHead) {
        ListNode slow = pHead;
        ListNode fast = pHead;
        while (fast !=null && fast.next !=null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) {
                break;
            }
        }
        if (fast == null || fast.next ==null) {
            // 不存在环
            return null;
        }
        fast = pHead;
        // 与第一次相遇的节点同速度前进 相遇的位置就是环入口
        while (slow != fast) {
            slow = slow.next;
            fast = fast.next;
        }

        return fast;
    }
}
